package tree;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/9 13:31
 * @description:  给定一颗二叉树和其中一个节点，找出中序遍历的下一个节点
 *  思路：如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点
 *       如果一个节点没有右子树的情形，如果节点是它父节点的
 */

 class TreeLinkNode{
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode parent = null;

    TreeLinkNode(int val){
        this.val = val;
    }
}
public class Next_node {

     public TreeLinkNode GetNext(TreeLinkNode node){
         if(node == null){
             return null;
         }
         TreeLinkNode next = null;
         if(node.right != null){
             TreeLinkNode tmp = node.right;
             //找到最左边的那个
             while (tmp.left!=null){
                 tmp = tmp.left;
             }
             next = tmp;
         }else if(node.parent!=null){   //节点没有右子树，
             TreeLinkNode n_parent = node.parent;
             TreeLinkNode curr_node = node;
             while (n_parent !=null && curr_node == n_parent.right){
                 curr_node = n_parent;
                 n_parent = n_parent.parent;
             }
             next = n_parent;
         }
         return next;
     }
}
